字节跳动夏令营笔试题记录。
题目链接
题目
- 三个单选，两个填空，有基础知识题、概率题(概率题做的太差，基本不会)
- 四个编程。
第一题：给一个正整数数组，每两个数之间的距离定义是：a[i]+a[j]-(j-i)，即a[i]+a[j]+i-j。其中i和j是两个数的下标，并且j>i。问任意两个数之间的距离最大是多少。
同样是用的暴力，有大佬只取前多少个数计算就过了。。。还是测试数据太水。
思路：如果用暴力的话，当第j位是两个数中的一个时，从第0位到第j-1位挨着试一遍，取最大的就行，这样是n方复杂度。
但是从第0位到第j-1位的过程可以优化，因为0到j-1位中，一定是a[i]+i最大的那个数被选中，所以在j进行循环时，就一直记录a[i]+i最大的那个。1
2
3
4
5
6
7
8#大佬的精简python
def cal(scores):
pre=-float('inf')
res=-float('inf')
for idx, score in enumerate(scores):
res=max(res,pre+score-idx)
pre=max(pre,score+idx)
return res第二题：给一个二维的01地图，1是陆地，计算有多少块陆地(上下左右或斜对角相邻就算联通)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
int row[8]={-1,-1,-1,0,0,1,1,1};
int col[8]={-1,0,1,-1,1,-1,0,1};
void cal(vector<vector<char>> &mapp,int i,int j,int nn,int mm){
mapp[i][j]='0';
for(int ii=0;ii<8;ii++){
int xx=i+row[ii];
int yy=j+col[ii];
if(xx>=0&&yy>=0&&xx<nn&&yy<mm){
if(mapp[xx][yy]=='1'){
cal(mapp,xx,yy,nn,mm);
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
const int nn=n,mm=m;
vector<vector<char>> mapp(nn,vector<char>(mm,'0'));
int tmp=0;
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
cin>>tmp;
mapp[i][j]='0'+tmp;
}
}
int sum=0;
for(int i=0;i<nn;i++){
for(int j=0;j<mm;j++){
if(mapp[i][j]=='1'){
sum++;
cal(mapp,i,j,nn,mm);
}
}
}
cout<<sum<<endl;
return 0;
}第三题：给定字符串：3$acm#,输出acmacmacm。
输入2%acm3%a##，输出acmaaaacmaaa。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
stack<char> sc;
string str;
cin>>str;
for(int i=0;i<str.size();i++){
if(str[i]>='0'&&str[i]<='9'){
sc.push(str[i]);
}else if(str[i]=='%'){
sc.push(str[i]);
}else if(str[i]=='#'){
string tmp="";
string now="";
char t;
while(sc.top()!='%'){
t=sc.top(); sc.pop();
tmp+=t;
}
reverse(tmp.begin(),tmp.end());
sc.pop();
int num=sc.top()-'0'; sc.pop();
for(int k=0;k<num;k++){
now+=tmp;
}
for(int l=0;l<now.size();l++){
sc.push(now[l]);
}
}else{
sc.push(str[i]);
}
}
string res;
while(!sc.empty()){
res.push_back(sc.top()); sc.pop();
}
reverse(res.begin(),res.end());
cout<<res<<endl;
return 0;
}第四题：没时间做，大佬说是2018 worldfinal的c题。